package database

import (
	"JoRedis/util"
	"fmt"
	"strconv"
)

const HEAD_VALUE = -1

// SkipList 跳表
type SkipList struct {
	headPtr  *skipNode
	levelNum int
	length   int
}

// 跳表节点
type skipNode struct {
	val      int
	downPtr  *skipNode
	rightPtr *skipNode
}

func MakeSkipList() *SkipList {
	skipListPtr := &SkipList{
		headPtr:  makeSkipNode(HEAD_VALUE, nil, nil),
		levelNum: 1,
	}
	return skipListPtr
}

func makeSkipNode(val int, rightPtr *skipNode, downPtr *skipNode) *skipNode {
	return &skipNode{
		val:      val,
		rightPtr: rightPtr,
		downPtr:  downPtr,
	}
}

// Add 添加节点
func (this *SkipList) Add(val int) {
	nodePtr := this.headPtr
	nodePtrSlc := make([]*skipNode, this.levelNum, this.levelNum)
	levelIdx := 0
	for {
		if nodePtr == nil {
			break
		}
		for {
			// 小于val,一直往右走
			if nodePtr.rightPtr != nil && nodePtr.rightPtr.val < val {
				nodePtr = nodePtr.rightPtr
			} else {
				break
			}
		}
		nodePtrSlc[levelIdx] = nodePtr
		levelIdx++
		// 大于val或者right为nil 向下走
		nodePtr = nodePtr.downPtr
	}
	levelIdx--
	nodePtr = nodePtrSlc[levelIdx]
	newNodePtr := makeSkipNode(val, nodePtr.rightPtr, nil)
	nodePtr.rightPtr = newNodePtr
	this.length++
	// 抛硬币决定是否生成索引
	this.addLevelIdx(newNodePtr, nodePtrSlc, levelIdx)
}

// addLevelIdx 抛硬币决定是否生成索引
func (this *SkipList) addLevelIdx(targetNodePtr *skipNode, nodePtrSlc []*skipNode, levelIdx int) {
	var randVal = getCoinRand()
	downPtr := targetNodePtr
	for {
		// randVal == 1 && this.levelNum < (this.length>>6)
		if randVal == 1 && this.length > 8 {
			if levelIdx > 0 {
				// 在现有的层级上增加新增的节点
				levelIdx--
				preNodePtr := nodePtrSlc[levelIdx]
				newNodePtr := makeSkipNode(targetNodePtr.val, preNodePtr.rightPtr, downPtr)
				preNodePtr.rightPtr = newNodePtr
				downPtr = newNodePtr
				randVal = getCoinRand()
			} else if this.levelNum < 3 {
				// 新增索引层
				newNodePtr := makeSkipNode(targetNodePtr.val, nil, downPtr)
				newHeadPtr := makeSkipNode(HEAD_VALUE, newNodePtr, this.headPtr)
				this.headPtr = newHeadPtr
				this.levelNum++
				break
			} else {
				break
			}
		} else {
			break
		}
	}
}

// Search 查找是否存在节点
func (this *SkipList) Search(val int) bool {
	nodePtr := this.get(val, this.headPtr)
	return nodePtr == nil
}

// Delete 删除节点
func (this *SkipList) Delete(val int) bool {
	exist := false
	nodePtr := this.headPtr
	for {
		nodePtr := this.get(val, nodePtr)
		if nodePtr != nil {
			nodePtr.rightPtr = nodePtr.rightPtr.rightPtr
			exist = true
			nodePtr = nodePtr.downPtr
		} else {
			break
		}
	}
	if exist {
		this.length = this.length - 1
		return true
	} else {
		return false
	}
}

// Print 打印
func (this *SkipList) Print() {
	nodePtr := this.headPtr
	levelHeadPtr := this.headPtr
	for {
		if nodePtr != nil {
			for {
				if nodePtr != nil {
					fmt.Printf(strconv.Itoa(nodePtr.val) + "____")
					if nodePtr.rightPtr != nil {
						nodePtr = nodePtr.rightPtr
					} else {
						break
					}
				} else {
					break
				}
			}
			fmt.Println()
			nodePtr = levelHeadPtr.downPtr
			levelHeadPtr = levelHeadPtr.downPtr
		} else {
			break
		}
	}
}

// get 获取等于val的左节点
func (this *SkipList) get(val int, fromNodePtr *skipNode) *skipNode {
	nodePtr := fromNodePtr
	for {
		if nodePtr == nil {
			break
		}
		for {
			// 当前值小于有节点的值那么一直往右
			if nodePtr.rightPtr != nil && nodePtr.rightPtr.val < val {
				nodePtr = nodePtr.rightPtr
			} else {
				break
			}
		}
		if nodePtr.rightPtr != nil && nodePtr.rightPtr.val == val {
			// 有节点相等
			return nodePtr
		}
		// 有节点比当前值大那么向下
		nodePtr = nodePtr.downPtr
	}
	return nil
}

// getCoinRand 获取硬币的随机值
func getCoinRand() int {
	return util.Rand(0, 2000) % 2
}
